#include <ctime>
#include <stdio.h>
#include <stdlib.h>
#include <sys/select.h>
#include <time.h>
#include "0.sort_test.h"

#define MAX_N 10000

void insert_sort(int *arr, int l, int r){
    int cn = 0;
	for(int i = l + 1; i < r; i++){
		int j = i;
        while(j > l && arr[j] < arr[j - 1]){
            swap(arr[j], arr[j - 1]);
            j -= 1;
            cn += 1;
        }
	}
    printf("\nswap times: %d\n", cn);
	return;
}

void unguarded_insert_sort(int *arr, int l, int r){
    int cn = 0;
    int idx = l;
    for(int i = l + 1; i < r; i++){
        if(arr[i] < arr[idx]) idx = i;
    }
    while(idx > l){
        swap(arr[idx], arr[idx - 1]);
        idx -= 1;
    }
    for(int i = l + 1; i < r; i++){
		int j = i;
        while(arr[j] < arr[j - 1]){
            swap(arr[j], arr[j - 1]);
            j -= 1;
            cn += 1;
        }
	}
    printf("\nswap times: %d\n", cn);
    
    return;
}

void mytest(){
    int a[] = {3, 4, 2, 1};
    int *arr = a;
    TEST(insert_sort, arr, 4);
    TEST(unguarded_insert_sort, arr, 4);
}

int main(){
    // mytest();
	int *arr = getRandData(SMALL_DATA_N);
	TEST(insert_sort, arr, SMALL_DATA_N);
    TEST(unguarded_insert_sort, arr, SMALL_DATA_N);
	free(arr);

	return 0;
}